#include "heap.h"



void HEInit(HE* he)
{
	assert(he);
	HEDataType* ret = (HEDataType*)malloc(sizeof(HEDataType) * MAX);
	if (!ret)
	{
		perror("malloc");
		return;
	}
	he->arr = ret;
	he->capacity = MAX;
	he->sz = 0;
	ret = NULL;
}
void HEDestry(HE* he)
{
	assert(he);
	free(he->arr);
	he->capacity = 0;
	he->sz = 0;
	he = NULL;
}

void HEPush(HE* he, HEDataType x)
{
	assert(he);
	if (he->sz == he->capacity)
	{
		HEDataType* ret = (HEDataType*)realloc(he->arr, sizeof(HEDataType) * he->capacity * 2);
		if (!ret)
		{
			perror("malloc");
			return;
		}
		he->arr = ret;
		he->capacity *= 2;
		ret = NULL;
	}
	he->arr[he->sz] = x;
	
	AdjustUp(he->arr, he->sz);
	he->sz++;
}
void HEPop(HE* he)
{
	assert(he);
	Swap(&he->arr[0], &he->arr[--he->sz]);
	AdjustDown(he->arr, he->sz, 0);
}

bool HEEmpty(HE* he)
{
	assert(he);
	return he->sz != 0;
}
HEDataType HETop(HE* he)
{
	assert(he);
	return he->arr[0];
}


int HeSize(HE* he)
{
	assert(he);
	return he->sz;
}

void Swap(HEDataType* p1, HEDataType* p2)
{
	HEDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
	tmp = NULL;
}



void AdjustUp(HEDataType* arr, int child)
{
	assert(arr);
	int father = (child - 1) / 2;
	while (child)
	{
		if (arr[father] < arr[child])
		{
			Swap(&arr[father], &arr[child]);
		}
		else
		{
			break;
		}
		child = father;
		father = (child - 1) / 2;
	}


}
void AdjustDown(HEDataType* arr, int n, int father)
{
	assert(arr);
	int child = father * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			Swap(&arr[child], &arr[child + 1]);
		}
		if (arr[father] < arr[child])
		{
			Swap(&arr[father], &arr[child]);
			father = child;
		}
		else
		{
			break;
		}
		child = father * 2 + 1;
	}
}